#!/usr/bin/python3
# coding:utf-8


class Stack(object):
    # 初始化栈为空列表
    def __init__(self):
        self.items = []

    # 判断栈是否为空，返回布尔值
    def is_empty(self):
        return self.items == []

    # 返回栈顶元素
    def peek(self):
        return self.items[len(self.items) - 1]

    # 返回栈的大小
    def size(self):
        return len(self.items)

    # 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）
    def push(self, item):
        self.items.append(item)

    # 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）
    def pop(self, item):
        return self.items.pop()


try:
    T = int(input())
    for t in range(T):
        n = int(input())
        x = input()
        s = Stack()
        flag = True
        popFlag = False
        lsFlag = False
        a = 0
        j = 0
        k = 0
        su = 0
        for i in x:
            if flag:
                if i == '(':
                    s.push(i)
                    flag = False
            else:
                if i == '(':
                    if popFlag:
                        j = j + 1
                        popFlag = False
                    s.push(i)
                    lsFlag = False
                else:
                    if not s.is_empty():
                        s.pop('(')
                        a = a + 1
                        popFlag = True
                        if not lsFlag:
                            if k != 0:
                                su = su + 2*k - 1
                                k = 0
                        k = k + 1
                        lsFlag = True
        if a == 1:
            su = 1
        else:
            su = (su + j) % 1000000007
        print("Case #%d: %d" % (t + 1, su))
except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
